package leetcode.fournineseven;

import java.util.*;

/**
 * Description:
 * Created By xxm
 */
public class Solution {
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];

        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                // find nums1'element in nums2 index
                // j is index
                if (nums2[j] == nums1[i]) {
                    for (int k = j; k < nums2.length; k++) {
                        if (nums2[k] > nums1[i]) {
                            res[i] = nums2[k];
                            break;
                        } else {
                            res[i] = -1;
                        }
                    }
                }
            }
        }

        return res;

    }

    public static int[] nextGreaterElementB(int[] findNums, int[] nums) {
        Map<Integer, Integer> map = new HashMap<>(); // map from x to next greater element of x
        Stack<Integer> stack = new Stack<>();
        for (int num : nums) {
            while (!stack.isEmpty() && stack.peek() < num)
                map.put(stack.pop(), num);
            stack.push(num);
        }
        for (int i = 0; i < findNums.length; i++)
            // 1->3 3->4
            findNums[i] = map.getOrDefault(findNums[i], -1); // (pattern key , lose pattern return) return value
        return findNums;
    }

    public static void main(String[] args) {
        int[] num1 = new int[]{4, 1, 2};
        int[] num2 = new int[]{1, 3, 4, 2};

        System.out.println(Arrays.toString(nextGreaterElementB(num1, num2)));

        int[] num3 = new int[]{2, 4};
        int[] num4 = new int[]{1, 2, 3, 4};

        System.out.println(Arrays.toString(nextGreaterElementB(num3, num4)));
    }

}
